package leetcode;

/**
 * Created by Ghost on 2014/12/1 0001.
 */
public class Jump_Game {
    /*public boolean canJump(int[] A) {//O(n^2)
        if(A==null ||A.length==0)
            return true;
        boolean[] B = new boolean[A.length];
        B[0]= true;
        for(int i=1;i<B.length;i++){
            for(int j = i-1;j>=0;j--){
                if(B[j] && A[j]>=i-j){
                    B[i] = true;
                    break;
                }
            }
        }
        return B[B.length-1];
    }
*/
    public boolean canJump(int[] A){//O(n)
        if(A==null ||A.length==0)
            return true;
        int end=0,current=0,farthest = A[0];
        int i=0;
        while(i<=farthest && i<=A.length-1){
            end = A[i]+i;
            if(end>farthest)
                farthest = end;
            i++;
        }

        if(farthest >= A.length-1)
            return true;
        else
            return false;
    }
    public static void main(String[] args){
        Jump_Game jump_game = new Jump_Game();
        int[] A = {2,3,1,1,4};
        System.out.println(jump_game.canJump(A));
    }
}
